{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Great Partitions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPartitions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #好分区的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组 <code>nums</code> 和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p><strong>分区</strong> 的定义是：将数组划分成两个有序的 <strong>组</strong> ，并满足每个元素 <strong>恰好</strong> 存在于 <strong>某一个</strong> 组中。如果分区中每个组的元素和都大于等于 <code>k</code> ，则认为分区是一个好分区。</p>\n",
    "\n",
    "<p>返回 <strong>不同</strong> 的好分区的数目。由于答案可能很大，请返回对 <code>10<sup>9</sup> + 7</code> <strong>取余</strong> 后的结果。</p>\n",
    "\n",
    "<p>如果在两个分区中，存在某个元素 <code>nums[i]</code> 被分在不同的组中，则认为这两个分区不同。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4], k = 4\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>好分区的情况是 ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) 和 ([4], [1,2,3]) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,3,3], k = 4\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>数组中不存在好分区。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [6,6], k = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>可以将 nums[0] 放入第一个分区或第二个分区中。\n",
    "好分区的情况是 ([6], [6]) 和 ([6], [6]) 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length, k &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-great-partitions](https://leetcode.cn/problems/number-of-great-partitions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-great-partitions](https://leetcode.cn/problems/number-of-great-partitions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]\\n4', '[3,3,3]\\n4', '[6,6]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < k * 2: return 0\n",
    "        mod = 10**9 + 7\n",
    "        dp = [1] + [0] * (k - 1)\n",
    "        for a in nums:\n",
    "            for i in range(k - 1 - a, -1, -1):\n",
    "                dp[i + a] += dp[i]\n",
    "        return (pow(2, len(nums), mod) - sum(dp) * 2 + mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < k * 2: return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * k\n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            for j in range(k - 1, x - 1, -1):\n",
    "                f[j] = (f[j] + f[j - x]) % MOD\n",
    "        return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        M = 10**9 + 7\n",
    "        if k > sum(nums) // 2:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        f = [0] * k\n",
    "        f[0] = 1\n",
    "        for v in nums:\n",
    "            for j in range(k-1, -1, -1):\n",
    "                if j-v >= 0:\n",
    "                    f[j] += f[j-v]\n",
    "                    f[j] %= M\n",
    "\n",
    "        ans = pow(2, n, M) - 2 * sum(f) % M\n",
    "        return ans % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        # 正难则反，定义坏分区为至少存在一个分区元素和< k的情况。\n",
    "        if sum(nums) < k * 2: return 0 # 特判后，只有两好和一坏一好的情况，如果出现坏分区，必定是一坏一好，不可能出现两坏，因此后面才能直接dp求坏分区的出现个数\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * k\n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            for j in range(k - 1, x - 1, -1):\n",
    "                f[j] = (f[j] + f[j - x]) % MOD\n",
    "        return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < k * 2: return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * k\n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            for j in range(k - 1, x - 1, -1):\n",
    "                f[j] = (f[j] + f[j - x]) % MOD\n",
    "        return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < k * 2:\n",
    "            return 0\n",
    "        dp, mod = [1] + [0 for _ in range(k - 1)], 10 ** 9 + 7\n",
    "        for x in nums:\n",
    "            for i in range(k - 1 - x, -1, -1):\n",
    "                dp[i + x] = (dp[i + x] + dp[i]) % mod\n",
    "        return (pow(2, len(nums) - 1, mod) - sum(dp)) * 2 % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        dp = [0]*k\n",
    "        s = sum(nums)\n",
    "        if s < 2*k:\n",
    "            return 0\n",
    "        dp[0] = 1\n",
    "        n = len(nums)\n",
    "        for num in nums:\n",
    "            for i in range(k-1, num-1, -1):\n",
    "                dp[i] += dp[i-num]\n",
    "        ans = pow(2, n, mod)\n",
    "        ans -= 2*sum(dp)\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < k * 2: return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [1] * k\n",
    "        for x in nums:\n",
    "            for j in range(k - 1, x - 1, -1):\n",
    "                f[j] = (f[j] + f[j - x]) % MOD\n",
    "        return (pow(2, len(nums), MOD) - f[-1] * 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < 2 * k:\n",
    "            return 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        f = [0] * k\n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            for j in range(k - 1, x - 1, -1):\n",
    "                f[j] += f[j - x]\n",
    "        \n",
    "        tot = pow(2, n, mod)\n",
    "        return (tot - (sum(f) * 2 % mod)) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        if s < 2 * k:\n",
    "            return 0\n",
    "        dp = [0] * k \n",
    "        dp[0] = 1 \n",
    "        for num in nums:\n",
    "            for t in range(k - 1, num - 1, - 1):\n",
    "                dp[t] += dp[t - num]\n",
    "                dp[t] %= 10 ** 9 + 7 \n",
    "        return ((1 << n) - sum(dp) * 2) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        dpls=[0 for i in range(k)]\n",
    "        dpls[0]=1\n",
    "        if sum(nums)<2*k:\n",
    "            return 0\n",
    "        for i in range(n):\n",
    "            if nums[i]>=k:\n",
    "                break\n",
    "            else:\n",
    "                gls=[0 for i in range(n)]\n",
    "                for j in range(k-nums[i]-1,-1,-1):\n",
    "                    dpls[j+nums[i]]+=+dpls[j]\n",
    "        return (pow(2,len(nums),10**9+7)-2*sum(dpls))%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < 2 * k:   return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [0] * k\n",
    "        dp[0] = 1\n",
    "        for num in nums:\n",
    "            for i in range(k-1, num - 1, -1):\n",
    "                dp[i] = (dp[i] + dp[i-num]) % MOD\n",
    "        return  (pow(2, len(nums), MOD) - sum(dp) * 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < 2 * k:\n",
    "            return 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        f = [0] * (k)\n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            for i in range(k - 1, x - 1, -1):\n",
    "                f[i] = (f[i] + f[i - x]) % mod\n",
    "        return (pow(2, n, mod) - sum(f) * 2 + mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        f = [0] * (k)\n",
    "        f[0] = 1\n",
    "        MOD = 10**9 + 7\n",
    "        if sum(nums) < 2 * k: return 0\n",
    "        for x in nums:\n",
    "            for i in range(k - 1, -1, -1):\n",
    "                if i >= x: f[i] += f[i - x]\n",
    "        return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < k * 2:\n",
    "            return 0\n",
    "        mod = 10**9 + 7\n",
    "        f = [0] * k\n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            for j in range(k - 1, x - 1, -1):\n",
    "                f[j] = (f[j] + f[j - x]) % mod\n",
    "        return (pow(2, len(nums), mod) - sum(f) * 2) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < k * 2: return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * k\n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            for j in range(k - 1, x - 1, -1):\n",
    "                f[j] = (f[j] + f[j - x]) % MOD\n",
    "        return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < k * 2: return 0\n",
    "        mod = 10**9 + 7\n",
    "        dp = [1] + [0] * (k - 1)\n",
    "        for a in nums:\n",
    "            for i in range(k - 1 - a, -1, -1):\n",
    "                dp[i + a] += dp[i]\n",
    "        return (pow(2, len(nums), mod) - sum(dp) * 2 + mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        if s < 2 * k:\n",
    "            return 0\n",
    "        dp = [0] * k \n",
    "        dp[0] = 1 \n",
    "        for num in nums:\n",
    "            for t in range(k - 1, num - 1, - 1):\n",
    "                dp[t] += dp[t - num]\n",
    "                dp[t] %= 10 ** 9 + 7 \n",
    "        return ((1 << n) - sum(dp) * 2) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "       if sum(nums) < k * 2: return 0\n",
    "       MOD = 10 ** 9 + 7\n",
    "       f = [0] * k\n",
    "       f[0] = 1\n",
    "       for x in nums:\n",
    "           for j in range(k - 1, x - 1, -1):\n",
    "               f[j] = (f[j] + f[j - x]) % MOD\n",
    "       return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9) + 7\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if k > sum(nums) / 2: return 0\n",
    "        \n",
    "        total = 1\n",
    "        n = len(nums)\n",
    "        for _ in range(n):\n",
    "            total = (total * 2) % MOD\n",
    "\n",
    "        dp = [0] * k\n",
    "        dp[0] = 1\n",
    "        for i in range(n):\n",
    "            new_dp = [0] * k\n",
    "            new_dp[0] = 1\n",
    "\n",
    "            for j in range(1, k):\n",
    "                cur = dp[j]\n",
    "                if j - nums[i] >= 0:\n",
    "                    cur = (cur + dp[j - nums[i]]) % MOD\n",
    "                new_dp[j] = cur\n",
    "            \n",
    "            dp = new_dp\n",
    "\n",
    "        neg = 2 * sum(dp) % MOD\n",
    "        return (total - neg) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        N = len(nums)\n",
    "        if sum(nums) < k*2: return 0\n",
    "        states = [1]*(k+1)\n",
    "        M = 10**9+7\n",
    "        for off, n in enumerate(nums, 1):\n",
    "            for _k in range(k, 0, -1):\n",
    "                if _k > n:\n",
    "                    states[_k] = (states[_k] + states[_k - n]) % M\n",
    "        return ((1<<N) - states[-1]*2) % M\n",
    "\n",
    "        # S[n][k] = S[n-1][k] + S[n-1][k-N[n]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < k * 2: return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [0] * k\n",
    "        dp[0] = 1\n",
    "        for x in nums:\n",
    "            for j in range(k - 1, x - 1, -1):\n",
    "                dp[j] = (dp[j] + dp[j - x]) % MOD\n",
    "        return (pow(2, len(nums), MOD) - sum(dp) * 2) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        mod=10**9+7\n",
    "        summ=sum(nums)\n",
    "        if summ-k<0:return 0\n",
    "        if summ<2*k:return 0\n",
    "        \n",
    "        dp=[0]*(k+1)\n",
    "        dp[0]=1\n",
    "        \n",
    "        \n",
    "        for i in nums:\n",
    "            for j in range(len(dp)-1,-1,-1):\n",
    "                if j-i<0:break\n",
    "                dp[j]+=dp[j-i]\n",
    "        \n",
    "        \n",
    "        print(dp)\n",
    "        \n",
    "        \n",
    "        return ((pow(2,n-1,mod)-sum(dp[:-1]))<<1)%mod\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < k * 2: return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * k\n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            for j in range(k - 1, x - 1, -1):\n",
    "                f[j] = (f[j] + f[j - x]) % MOD\n",
    "        return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < k * 2: return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * k\n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            for j in range(k - 1, x - 1, -1):\n",
    "                f[j] = (f[j] + f[j - x]) % MOD\n",
    "        return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < k * 2: return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * k\n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            for j in range(k - 1, x - 1, -1):\n",
    "                f[j] = (f[j] + f[j - x]) % MOD\n",
    "        return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        m,n=sum(nums),len(nums)\n",
    "        mod=pow(10,9)+7\n",
    "        if min(nums)>=k:\n",
    "            return pow(2,n,mod)-2\n",
    "        if m<k+k:\n",
    "            return 0\n",
    "        dp=[0]*k\n",
    "        dp[0]=1\n",
    "        for x in nums:\n",
    "            for j in range(k-1,x-1,-1):\n",
    "                dp[j]=dp[j]+dp[j-x]\n",
    "                dp[j]%=mod\n",
    "        return (pow(2,len(nums),mod)-sum(dp)*2)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < k * 2: return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * k\n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            for j in range(k - 1, x - 1, -1):\n",
    "                f[j] = (f[j] + f[j - x]) % MOD\n",
    "        return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < k * 2: return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = [0] * k\n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            for j in range(k - 1, x - 1, -1):\n",
    "                f[j] = (f[j] + f[j - x]) % MOD\n",
    "        return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        # cnts = [[0 for j in range(k + 1)] for i in range(k + 1)]\n",
    "        # cnts[0][0] = 1\n",
    "        # lst = [[0, 0]]\n",
    "        free_arr = [0 for i in range(k)]\n",
    "        row = [0 for i in range(k)]\n",
    "        col = [0 for i in range(k)]\n",
    "        free_arr[0] = 1\n",
    "        sum_val = 0\n",
    "        res = 0\n",
    "        mod = 1000000007\n",
    "        for v in nums:\n",
    "            nfree_arr = [0 for i in range(k)]\n",
    "            nrow = [0 for i in range(k)]\n",
    "            ncol = [0 for i in range(k)]\n",
    "            nres = 0\n",
    "            for x in range(k):\n",
    "                if free_arr[x] == 0:\n",
    "                    continue\n",
    "                y = sum_val - x\n",
    "                if x + v >= k:\n",
    "                    nrow[y] += free_arr[x]\n",
    "                    nrow[y] %= mod\n",
    "                else:\n",
    "                    nfree_arr[x + v] += free_arr[x]\n",
    "                    nfree_arr[x + v] %= mod\n",
    "\n",
    "                if y + v >= k:\n",
    "                    ncol[x] += free_arr[x]\n",
    "                    ncol[x] %= mod\n",
    "                else:\n",
    "                    nfree_arr[x] += free_arr[x]\n",
    "                    nfree_arr[x] %= mod\n",
    "            \n",
    "            for i in range(k):\n",
    "                if row[i] != 0:\n",
    "                    nrow[i] += row[i]\n",
    "                    nrow[i] %= mod\n",
    "                    if i + v >= k:\n",
    "                        nres += row[i]\n",
    "                        nres %= mod\n",
    "                    else:\n",
    "                        nrow[i + v] += row[i]\n",
    "                        nrow[i + v] %= mod\n",
    "                \n",
    "                if col[i] != 0:\n",
    "                    ncol[i] += col[i]\n",
    "                    ncol[i] %= mod\n",
    "\n",
    "                    if i + v >= k:\n",
    "                        nres += col[i]\n",
    "                        nres %= mod\n",
    "                    else:\n",
    "                        ncol[i + v] += col[i]\n",
    "                        ncol[i + v] %= mod\n",
    "\n",
    "            if res != 0:\n",
    "                nres += res * 2\n",
    "                nres %= mod\n",
    "            \n",
    "            res = nres\n",
    "            free_arr = nfree_arr\n",
    "            row = nrow\n",
    "            col = ncol\n",
    "\n",
    "            sum_val += v\n",
    "            \n",
    "        return res % 1000000007\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        # cnts = [[0 for j in range(k + 1)] for i in range(k + 1)]\n",
    "        # cnts[0][0] = 1\n",
    "        # lst = [[0, 0]]\n",
    "        free_arr = [0 for i in range(k)]\n",
    "        row = [0 for i in range(k)]\n",
    "        col = [0 for i in range(k)]\n",
    "        free_arr[0] = 1\n",
    "        sum_val = 0\n",
    "        res = 0\n",
    "        for v in nums:\n",
    "            nfree_arr = [0 for i in range(k)]\n",
    "            nrow = [0 for i in range(k)]\n",
    "            ncol = [0 for i in range(k)]\n",
    "            nres = 0\n",
    "            for i in range(k):\n",
    "                if free_arr[i] == 0:\n",
    "                    continue\n",
    "                i2 = sum_val - i\n",
    "\n",
    "                x = i\n",
    "                y = i2\n",
    "\n",
    "                xx = x + v\n",
    "                yy = y\n",
    "\n",
    "                if xx >= k:\n",
    "                    nrow[yy] += free_arr[i]\n",
    "                else:\n",
    "                    nfree_arr[xx] += free_arr[i]\n",
    "\n",
    "\n",
    "                xx = x\n",
    "                yy = y + v\n",
    "                if yy >= k:\n",
    "                    ncol[xx] += free_arr[i]\n",
    "                else:\n",
    "                    nfree_arr[xx] += free_arr[i]\n",
    "            \n",
    "            for i in range(k):\n",
    "                if row[i] != 0:\n",
    "                    nrow[i] += row[i]\n",
    "\n",
    "                    if i + v >= k:\n",
    "                        nres += row[i]\n",
    "                    else:\n",
    "                        nrow[i + v] += row[i]\n",
    "                \n",
    "                if col[i] != 0:\n",
    "                    ncol[i] += col[i]\n",
    "\n",
    "                    if i + v >= k:\n",
    "                        nres += col[i]\n",
    "                    else:\n",
    "                        ncol[i + v] += col[i]\n",
    "\n",
    "            if res != 0:\n",
    "                nres += res * 2\n",
    "            \n",
    "            res = nres\n",
    "            free_arr = nfree_arr\n",
    "            row = nrow\n",
    "            col = ncol\n",
    "\n",
    "\n",
    "\n",
    "            sum_val += v\n",
    "            \n",
    "        return res % 1000000007\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        if sum(nums) < 2 * k:\n",
    "            return 0 \n",
    "        n = len(nums)\n",
    "        Mod = int(1e9+7)\n",
    "        dp = [[0] * (k) for _ in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            dp[i][0] = 1\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1, k):\n",
    "                if j >= nums[i-1]:\n",
    "                    dp[i][j] = (dp[i-1][j] + dp[i-1][j-nums[i-1]]) % Mod \n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] \n",
    "        tot = 0\n",
    "        for j in range(k):\n",
    "            tot += dp[n][j]\n",
    "        return (pow(2, n, Mod) - 2 * tot + Mod) % Mod "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "如果一个元素出现次数超过2次，那么一定没有好分区\n",
    "\n",
    "# 子序列-->\n",
    "暴力枚举一组中的所有可能的话，一共是2^n\n",
    "1，2，3，4，5\n",
    "如果知道了前一组的和，后一组的和自然就能算出来，并且，为了让答案合法，前一组必须将所有数组出现了两次的数都包括在内。注意到k非常小，但是sum(nums)可能非常大\n",
    "\n",
    "逆向思维：找出和小于k的子序列的合法子序列所有组合可能(包括什么都不选)，然后用所有合法组合可能减去这些，就是答案,\n",
    "由于考虑重复元素比较复杂，这里将重复元素排除的话，答案为\n",
    "2^n-(?)*2\n",
    "如果有重复元素 y个,注意由于这些元素都必须选，会对背包的k产生影响\n",
    "背包问题 f[i][k]=f[i-1][k-nums[i]]+f[i-1][k]，注意有些数字必须选，否则不合法\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        m=len(nums)\n",
    "        if sum(nums)<2*k :return 0 #特判，防止重复统计\n",
    "        f=[[0]*(k) for _ in range(m+1)] #+1有深意\n",
    "        f[0][0]=1\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                f[i+1][j]=f[i][j]\n",
    "                if j-nums[i]>=0:\n",
    "                    f[i+1][j]+=f[i][j-nums[i]]\n",
    "        sub=0\n",
    "        for i in range(k):\n",
    "            sub+=f[m][i]\n",
    "        ans=pow(2,m,MOD)\n",
    "        return (ans-sub*2)%MOD\n",
    "\n",
    "\n",
    "         \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "如果一个元素出现次数超过2次，那么一定没有好分区\n",
    "\n",
    "# 子序列-->\n",
    "暴力枚举一组中的所有可能的话，一共是2^n\n",
    "1，2，3，4，5\n",
    "如果知道了前一组的和，后一组的和自然就能算出来，并且，为了让答案合法，前一组必须将所有数组出现了两次的数都包括在内。注意到k非常小，但是sum(nums)可能非常大\n",
    "\n",
    "逆向思维：找出和小于k的子序列的合法子序列所有组合可能(包括什么都不选)，然后用所有合法组合可能减去这些，就是答案,\n",
    "由于考虑重复元素比较复杂，这里将重复元素排除的话，答案为\n",
    "2^n-(?)*2\n",
    "如果有重复元素 y个,注意由于这些元素都必须选，会对背包的k产生影响\n",
    "背包问题 f[i][k]=f[i-1][k-nums[i]]+f[i-1][k]，注意有些数字必须选，否则不合法\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        m=len(nums)\n",
    "        if sum(nums)<2*k :return 0\n",
    "        f=[[0]*(k) for _ in range(m+1)] #+1有深意\n",
    "        f[0][0]=1\n",
    "        for i in range(m):\n",
    "            for j in range(k):\n",
    "                f[i+1][j]=f[i][j]\n",
    "                if j-nums[i]>=0:\n",
    "                    f[i+1][j]+=f[i][j-nums[i]]\n",
    "        sub=0\n",
    "        for i in range(k):\n",
    "            sub+=f[m][i]\n",
    "        return (2**m-sub*2)%MOD\n",
    "\n",
    "\n",
    "         \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        if sum(nums)<2*k: return 0\n",
    "        dp = [[0]*k for _ in range(n+1)]\n",
    "\n",
    "        MODX = 10**9+7\n",
    "\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(k):\n",
    "        \n",
    "                dp[i][j] = dp[i-1][j]+(dp[i-1][j-nums[i-1]] if j>=nums[i-1] else 0)\n",
    "                dp[i][j] %=MODX\n",
    "        \n",
    "        return (pow(2,n,MODX)-sum(dp[n])*2 )%MODX\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        m,n=sum(nums),len(nums)\n",
    "        mod=pow(10,9)+7\n",
    "        if min(nums)>=k:\n",
    "            return pow(2,n,mod)-2\n",
    "        if m<k+k:\n",
    "            return 0\n",
    "        dp=[[0 for _ in range(k)] for _ in range(n+1)]\n",
    "        dp[0][0]=1\n",
    "        for i,x in enumerate(nums):\n",
    "            for j in range(k):\n",
    "                if j>=x:\n",
    "                    dp[i+1][j]=dp[i][j]+dp[i][j-x]\n",
    "                else:\n",
    "                    dp[i+1][j]=dp[i][j]\n",
    "                dp[i+1][j]%=mod\n",
    "        return (pow(2,len(nums),mod)-sum(dp[-1])*2)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        m,n=sum(nums),len(nums)\n",
    "        mod=pow(10,9)+7\n",
    "        if min(nums)>=k:\n",
    "            return pow(2,n,mod)-2\n",
    "        if m<k+k:\n",
    "            return 0\n",
    "        dp=[[0 for _ in range(k)] for _ in range(n+1)]\n",
    "        dp[0][0]=1\n",
    "        for i,x in enumerate(nums):\n",
    "            if x>k:\n",
    "                dp[i+1]=dp[i]\n",
    "                continue\n",
    "            for j in range(k):\n",
    "                if j>=x:\n",
    "                    dp[i+1][j]=dp[i][j]+dp[i][j-x]\n",
    "                else:\n",
    "                    dp[i+1][j]=dp[i][j]\n",
    "                dp[i+1][j]%=mod\n",
    "        return (pow(2,len(nums),mod)-sum(dp[-1])*2)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if sum(nums) < 2* k:\n",
    "            return 0 \n",
    "        Mod = int(1e9+7)\n",
    "\n",
    "        dp = [[0] *(k+1) for _ in range(n + 1)]\n",
    "        for i in range(1, k+1):\n",
    "            dp[0][i] = 1 \n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            for c in range(1, k+1):\n",
    "                dp[i][c] = dp[i-1][c] + dp[i-1][max(c-nums[i-1], 0)]\n",
    "\n",
    "        return (pow(2, n, Mod) - 2 * dp[n][k] + Mod) % Mod \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        M=int(1e9+7)\n",
    "        up_dp=[[0]*(k+1) for _ in range(n)]\n",
    "        down_dp=[[0]*(k+1) for _ in range(n)]\n",
    "        if nums[0]>=k:\n",
    "            for i in range(k+1):\n",
    "                up_dp[0][i]=1\n",
    "        else:\n",
    "            for i in range(nums[0]+1):\n",
    "                up_dp[0][i]=1\n",
    "            for j in range(nums[0]+1,k+1):\n",
    "                down_dp[0][j]=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>=k:\n",
    "                for j in range(k+1):\n",
    "                    up_dp[i][j]=(up_dp[i-1][0]+1+up_dp[i-1][j])%M\n",
    "                    down_dp[i][j]=down_dp[i-1][j]\n",
    "            else:\n",
    "                for j in range(nums[i]+1):\n",
    "                    up_dp[i][j]=(up_dp[i-1][0]+1+up_dp[i-1][j])%M\n",
    "                    down_dp[i][j]=down_dp[i-1][j]\n",
    "                for j in range(nums[i]+1,k+1):\n",
    "                    up_dp[i][j]=(up_dp[i-1][j-nums[i]]+up_dp[i-1][j])%M\n",
    "                    down_dp[i][j]=(down_dp[i-1][j-nums[i]]+1+down_dp[i-1][j])%M\n",
    "        # print(up_dp)\n",
    "        # print(down_dp)\n",
    "        ans=(up_dp[n-1][k]-down_dp[n-1][k]-1+M)%M\n",
    "        s=sum(nums)\n",
    "        if s<2*k:\n",
    "            ans=0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPartitions(self, nums: List[int], k: int) -> int:\n",
    "        s=sum(nums)\n",
    "        if s<2*k:\n",
    "            return 0\n",
    "        n=len(nums)\n",
    "        M=int(1e9+7)\n",
    "        up_dp=[[0]*(k+1) for _ in range(n)]\n",
    "        down_dp=[[0]*(k+1) for _ in range(n)]\n",
    "        if nums[0]>=k:\n",
    "            for i in range(k+1):\n",
    "                up_dp[0][i]=1\n",
    "        else:\n",
    "            for i in range(nums[0]+1):\n",
    "                up_dp[0][i]=1\n",
    "            for j in range(nums[0]+1,k+1):\n",
    "                down_dp[0][j]=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>=k:\n",
    "                for j in range(k+1):\n",
    "                    up_dp[i][j]=(up_dp[i-1][0]+1+up_dp[i-1][j])%M\n",
    "                    down_dp[i][j]=down_dp[i-1][j]\n",
    "            else:\n",
    "                for j in range(nums[i]+1):\n",
    "                    up_dp[i][j]=(up_dp[i-1][0]+1+up_dp[i-1][j])%M\n",
    "                    down_dp[i][j]=down_dp[i-1][j]\n",
    "                for j in range(nums[i]+1,k+1):\n",
    "                    up_dp[i][j]=(up_dp[i-1][j-nums[i]]+up_dp[i-1][j])%M\n",
    "                    down_dp[i][j]=(down_dp[i-1][j-nums[i]]+1+down_dp[i-1][j])%M\n",
    "        # print(up_dp)\n",
    "        # print(down_dp)\n",
    "        ans=(up_dp[n-1][k]-down_dp[n-1][k]-1+M)%M\n",
    "        \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
